package com.jia.leetCode;

/**
 * 450. 删除二叉搜索树中的节点
 *
 *
 *
 */
public class Pro0450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) { return null; }
        if(key < root.val) {
            root.left = deleteNode(root.left, key);
        }else if(key > root.val) {
            root.right = deleteNode(root.right, key);
        }else {
            //key = root.key //删除节点root
            if(root.left == null) { //左孩子为null
                return root.right;
            }else if(root.right == null) {
                //右孩子为null
                return root.left;
            }else{
                //左右孩子都不为null
                TreeNode successor = min(root.right); //找到root的右子树的最小节点，即后继
                successor.right = deleteMin(root.right);//删除右子树最小节点
                successor.left = root.left;
                return successor;
            }
        }
        return root;
    }
    //删除二叉搜索树node的最小节点，并把树的根节点返回
    private TreeNode deleteMin(TreeNode node) {
        if(node == null) return null;
        if(node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }
    //找到二分搜索树node的最小节点
    private TreeNode min(TreeNode node) {
        if(node == null) { return null; }
        if(node.left == null) {
            return node;
        }
        return min(node.left);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node3 = new TreeNode(3);
        TreeNode node6 = new TreeNode(6);
        root.left = node3;
        root.right = node6;
        node3.left = new TreeNode(2);
        node3.right = new TreeNode(4);
        node6.right = new TreeNode(7);
        Pro0450 pro0450 = new Pro0450();
        System.out.println(pro0450.min(root).val);;
//        TreeNode treeNode = pro0450.deleteMin(root);
        TreeNode treeNode = pro0450.deleteNode(root, 3);
        System.out.println("aa");
    }
}
